package vno.sci
{
	import flash.geom.Point;
	import flash.media.ID3Info;
	import flash.utils.ByteArray;
	
	import vno.fux.ExPoint;
	import vno.sci.mapEditor.BuildingBuoy;
	import vno.sci.mapEditor.BuildingInfo;
	import vno.sci.mapEditor.IPoint;

	/**
	 * 返回在一个矩形区域里的点
	 * 用init初始化。
	 * 用showTest返回给定矩形内的点。 
	 * @author scinart
	 * 
	 */
	public class Util
	{
		private var vp_x:Vector.<BuildingInfo>;
		private var vp_y:Vector.<BuildingInfo>;
		public  function Util(vector:Vector.<BuildingInfo>)
		{
			if(vp_x==null)
			{
				var compareByX:Function = function (a:BuildingInfo, b:BuildingInfo):Number
				{
					return a.x - b.x;
				};
				var compareByY:Function = function (a:BuildingInfo, b:BuildingInfo):Number
				{
					return a.y - b.y;
				} 
				vp_x = vector.sort(compareByX).slice(0,vector.length);
				vp_y = vector.sort(compareByY).slice(0,vector.length);
			}
			else
			{
				throw new Error("vno.sci.init can only be called once.");
			}
		}
		/**
		 * 前置，必须满足topLeft.x<bottomRight.x && topLeft.y<bottomRight.y;
		 * @param m 矩形区域的宽度
		 * @param n 矩形区域的高度
		 * @param topLeft 左上角的点
		 * @param bottomRight 右下角的点
		 * @return 在矩形内的点的集合
		 * 
		 */		
		public function showTest(m:int, n:int, topLeft:IPoint, bottomRight:IPoint):Vector.<BuildingInfo>
		{
			var showWidth:int = Math.abs(topLeft.x - bottomRight.x);
			var showHeight:int = Math.abs(topLeft.y - bottomRight.y);
			
			// if showWidth/m > showHeight/n
			// 用Point.y
			// else 用Point.x
			if (showWidth*n - showHeight*m > 0)
			{
				var beginIndex:int = binarySearchLessThan(vp_y,0,vp_y.length,function(p:BuildingInfo):int
				{
					return RoundUp(topLeft.y - p.y);
				});
				var endIndex:int = binarySearchLessThan(vp_y,0,vp_y.length,function(p:BuildingInfo):int
				{
					return RoundUp(bottomRight.y - p.y);
				});
				var sub:Vector.<BuildingInfo> = vp_y.slice(beginIndex+1,endIndex+1);
				var subsub:Vector.<BuildingInfo> =	sub.filter(function(p:BuildingInfo, index:int, arr:Vector.<BuildingInfo>):Boolean
														{
															return p.x>= topLeft.x && p.x <= bottomRight.x;
														},null);
				return subsub;
			}
			else
			{
				var _beginIndex:int = binarySearchLessThan(vp_x,0,vp_x.length,function(p:BuildingInfo):int
				{
					return RoundUp(topLeft.x - p.x);
				});
				var _endIndex:int = binarySearchLessThan(vp_x,0,vp_x.length,function(p:BuildingInfo):int
				{
					return RoundUp(bottomRight.x - p.x);
				});
				var _sub:Vector.<BuildingInfo> = vp_x.slice(_beginIndex+1,_endIndex+1);
				var _subsub:Vector.<BuildingInfo> =	_sub.filter(function(p:BuildingInfo, index:int, arr:Vector.<BuildingInfo>):Boolean
				{
					return p.y>= topLeft.y && p.y <= bottomRight.y;
				});
				return _subsub;
			}
		}
		/**
		 * 
		 * @param array 支持array[i]操作的Array或者Vector或者其他，并且array是按lessthan排序的。即若lessthan(array[i])<0 implies lessthan(array[i+1])<0;
		 * @param begin 搜索区间，[begin,end)
		 * @param end  搜索区间，[begin,end)
		 * @param lessthan 参数类型同array[i], 返回值:int
		 *  将查找元素q与参数p比较，返回int, 若int<0, 视为q<p; 若int>0, 视为q>p; 若int=0, 视为q=p;
		 * @return 所查找元素的下标，若未找到返回-1;
		 * 
		 */		
		private function binarySearch(array:Object, begin:int, end:int, lessthan:Function):int
		{
			if (lessthan(array[begin]) < 0)
			{
				return -1;
			}
			if (lessthan(array[end-1]) > 0)
			{	
				return -1;
			}
			var mid:int = Math.floor((begin+end)/2);
			var t:int = lessthan(array[mid]); 
			while(t!= 0 && (begin<end))
			{
				
				if(t<0)//比mid小
				{
					end = mid;
				}
				else // 比mid大
				{
					begin = mid+1;
				}
				mid = Math.floor((begin+end)/2);
				t = lessthan(array[mid]);
			}
			if(t==0)
			{
				return mid;
			}
			else
			{
				return -1;
			}
		}
		/**
		 * 
		 * @param array 支持array[i]操作的Array或者Vector或者其他
		 * @param begin 搜索区间，[begin,end)
		 * @param end  搜索区间，[begin,end)
		 * @param lessthan 参数类型同array[i], 返回值:int
		 *  将查找元素q与参数p比较，返回int, 若int<0, 视为q<p; 若int>0, 视为q>p; 若int=0, 视为q=p;
		 * @return 最大的lessthan返回>0的下标
		 * 
		 */		
		private function binarySearchLessThan(array:Object, begin:int, end:int, lessthan:Function):int
		{
			//注释，下一行为<也行。
			if (lessthan(array[begin]) <= 0)
			{
				return -1;
			}
			if (lessthan(array[end-1]) > 0)
			{	
				return end-1;
			}
			var mid:int = Math.floor((begin+end)/2);
			var t:int = lessthan(array[mid]); 
			while(begin<end)
			{
				
				if(t<=0)//比mid小
				{
					end = mid;
				}
				else // 比mid大
				{
					begin = mid+1;
				}
				mid = Math.floor((begin+end)/2);
				t = lessthan(array[mid]);
			}
			return mid-1;
		}
		/**
		 * round away from zero. 
		 */		
		private function RoundUp(x:Number):int
		{
			if(x<0)
				return Math.floor(x);
			if(x>0)
				return Math.ceil(x);
			return 0;
		}
	}
}